package imooc_math.graph;

import java.util.Stack;
import java.util.Vector;

public class Path {
	public int s;
	public int[] from;
	Graph g;
	boolean[] visited;
	public Path(Graph g,int s){
		this.g = g;
		this.s = s;
		from = new int[g.V()];
		visited = new boolean[g.V()];
		for(int i=0;i<g.V();i++){
			visited[i] = false;
			from[i] = -1;
		}				
		dfs(s);				
	}
	public void dfs(int v){
		visited[v] = true;
		for(int i:g.adj(v)){
			if(!visited[i]){
				from[i] = v;
				dfs(i);
			}
		}		
	}
	public boolean hasPath(int w){
		return visited[w];
	}
	public Vector path(int w){
		Vector vector = new Vector();
		Stack<Integer> stack = new Stack<Integer>();
		int p = w;
		while(p != -1){
			stack.push(p);
			p = from[p];
		}
		while(!stack.isEmpty()){
			vector.add(stack.pop());
		}
		return vector;
	}
	public void showPath(int w){
		Vector vector = path(w);
		for(int i=0;i<vector.size();i++){
			System.out.print(vector.elementAt(i));
			if(i == vector.size()-1){
				System.out.println();
			}else{
				System.out.print("->");
			}
		}
	}
}
